|
1.
线对象邻接关系快速重构算法
廖名学 范植华 何晓新
计算机应用
给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O(n*n)；理论最好时间复杂度为O(C)，其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O(n(1+1/r))，r为算法分配的桶数量与n的比，空间复杂度为O(n)。证明了若不允许使用额外空间，则不可能使用排序算法解决该问题；给出了允许使用额外空间条件下的两遍排序算法，时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。
相关文章 |
多维度评价
|
